# from strsimpy.normalized_levenshtein import NormalizedLevenshtein


class NormalizedLevenshtein:
    def similarity(self, s1, s2):
        dist = self._levenshtein_distance(s1, s2)
        max_len = max(len(s1), len(s2))
        if max_len == 0:
            return 1.0
        return 1.0 - dist / max_len

    def distance(self, s1, s2):
        return 1.0 - self.similarity(s1, s2)

    def _levenshtein_distance(self, s1, s2):
        if len(s1) < len(s2):
            s1, s2 = s2, s1
        if len(s2) == 0:
            return len(s1)
        # previous_row=[0,1,2,3,4]
        previous_row = list(range(len(s2) + 1))
        for i, c1 in enumerate(s1):
            current_row = [i + 1]
            for j, c2 in enumerate(s2):
                # 插入操作注是上一个j+1的位置加1
                insertions = previous_row[j + 1] + 1
                # 删除操作  当前行的位置值加1
                deletions = current_row[j] + 1
                # 替换操作 上一行j的位置 加()
                substitution = previous_row[j] + (c1 != c2)
                current_row.append(min(insertions, deletions, substitution))
            previous_row = current_row
        return previous_row[-1]


normalizedLevenshtein = NormalizedLevenshtein()
query = "aa"
content = "aa"
# 1.先计算最小编辑距离 2 归一化 3 1-距离得到相似度
print(normalizedLevenshtein._levenshtein_distance(query, content))  # 3
print(normalizedLevenshtein.similarity(query, content))  # 1.0 越相似越高
print(normalizedLevenshtein.distance(query, content))  # 0 距离越短越相似
